<!DOCTYPE html>
<html lang="zh-cn">
<head>
    <meta charset="utf-8" />
    <title>整除, 最大公约数, 素数</title>
    <link rel="stylesheet" href="../../css/note.css"/>
</head>
<body>

<h2>整除</h2>

<p class="remark">
    记号: 整数集 `ZZ`, 非零整数集 `ZZ^**`, 正整数集 `ZZ^+`.
    以下若无特殊说明, `a, b, c, m, n` 等均表示整数.
</p>

<p class="definition">
    设 `n, d` 为整数, 若存在整数 `k` 使得 `n = k d`, 则记 `d | n`, 读作
    `d` <b>整除</b> `n`. 我们也说 `d` 是 `n` 的因子 (factor) 或约数
    (denominator) 或除数 (divisor), 也可以说 `n` 是 `d` 的倍数.
    若 `d` 不能整除 `n`, 则记 `d !| n`.
</p>

<p class="corollary">
    对任意整数 `d`, `d | 0` 总是成立; 若 `0 | n`, 则 `n = 0`.
</p>

<p class="corollary" id="cor-ka|kb">
	`(AA k in ZZ^**)` `a | b` `iff k a | k b`.
</p>

<p class="corollary" id="cor-div-order">
    `a | b rArr |a| le |b|` 或 `b = 0`.
    这表明非零整数的因子只有有限个.
    此外, 这个结论还用于带余除法的证明中.
</p>

<p class="proof">
    设 `b = k a`, 且 `b != 0`. 这推出 `k != 0`,
    因此 `|k| ge 1`, 从而 `|b| = |k| |a| ge |a|`.
</p>

<ol class="property">
    对任意整数 `a, b, c`,
	<li>`a | b` `iff |a|` 整除 `|b|`;</li>
	<li>`a | b` `and b | c` `rArr a | c`;</li>
	<li>`a | b` `and b | a` `rArr |a| = |b|`;</li>
	因此, 整除关系 "`|`" 构成 `ZZ^+` 上的偏序.
    在数论中, 我们常用 `a | b and b | a` 来证明两个正整数相等.
</ol>

<p class="proof">
    只证 3. 若 `a = 0`, 由 `a | b` 知 `b` 也等于零, 结论自然成立;
    `b = 0` 时同理. 下设 `a, b` 都不为零,
    由<a class="ref" href="#cor-div-order"></a>有
    <span class="formula">
        `|a| le |b|`, `quad |b| le |a|`,
    </span>
    因此结论成立.
</p>

<p class="proposition">
	设 `b in ZZ^**`, 它的全体 (正) 因子是 `{d_1, d_2, cdots, d_k}`,
	则 `{b//d_1, b//d_2, cdots, b//d_k}` 也是它的全体 (正) 因子.
</p>

<p class="proof">
	只证结论一, 结论二类似.
	设 `d_i | b`, 则 `b = d_i (b // d_i)`, 且 `b//d_i in ZZ^**`.
	所以 `b//d_i | b`. 另一方面, `d_i != d_j` 时, 有 `b//d_i != b//d_j`.
	所以 `b//d_1, b//d_2, cdots, b//d_k` 是 `b` 的 `k` 个不同的因子,
	即为 `b` 的全体因子.
</p>

<h2>最大公约数</h2>

<h3>定义</h3>

<p class="definition">
    若 `d | a`, `d | b`, 则 `d` 称为 `a, b` 的<b>公约数</b>.
    `a, b` 不全为零时, 它们的公约数只有有限个, 我们称其中最大的为 `a, b`
    的<b>最大公约数 (greatest common divisor)</b>, 记为 `gcd(a, b)`
    或 `(a, b)`;
    为使最大公约数的性质普遍成立, 我们规定 `(0, 0) = 0`.
</p>

<p class="definition">
    若 `a | h`, `b | h`, 则 `h` 称为 `a, b` 的<b>公倍数</b>.
    `a, b` 中有一个为零时, 平凡地有 `h = 0`; 若 `a, b != 0`,
    则 `a, b` 的全体公倍数中存在最小正整数, 称为 `a, b`
    的<b>最小公倍数 (least common multiple)</b>, 记为 `lcm(a, b)`
    或 `[a, b]`.
</p>

<p class="remark">
    类似可以定义 `n` 个整数 `a_1, a_2, cdots, a_n` 的 (最大) 公约数和
    (最小) 公倍数.
    本节的许多结论容易推广到任意有限个整数的情形, 简明起见不再赘述.
</p>

<h3>计算</h3>

<ol class="property" id="ppt-gcd">
    设 `d = (a_1, a_2, cdots, a_n)`, 则
	<li>`d = (a_1, a_2+k a_1, cdots, a_n)`, `AA k in ZZ`;</li>
	<li>`d = (a_1, a_2, cdots, a_n, 0)`;</li>
    <li>`d = (|a_1|, |a_2|, cdots, |a_n|)`;</li>
    <li><b>交换律</b> `d = (a_(i_1), a_(i_2), cdots, a_(i_n))`,
        `i_1, i_2, cdots, i_n` 是
		`1, 2, cdots, n` 的一个排列;
	</li>
    <li><b>结合律</b> `d = (a_1, a_2, cdots, a_n) = ((a_1, a_2), cdots, a_n)`;</li>
    <li><b>同乘非零常数</b> `k(a_1, a_2, cdots, a_n) = (k a_1, k a_2, cdots, k a_n)`, `k in ZZ^+`;</li>
    其中 3 到 6 也适用于最小公倍数.
</ol>

<ul class="proof">
    只证最后两条.
    <li>若 `d` 是 `a_1, a_2, cdots, a_n` 的公约数, 则 `d` 当然也是 `a_1,
        a_2` 的公约数, 从而 `d | (a_1, a_2)`, `d | a_i`, `i = 3, cdots,
        n`; 反过来, 若 `d | (a_1, a_2)`, `d | a_i`, `i = 3, cdots, n`,
        由定义即知 `d | a_i`, `i = 1, cdots, n`. 这证明了
        `a_1, cdots, a_n` 的全体公约数集合等于
        `(a_1, a_2), cdots, a_n` 的全体公约数集合,
        从而结论成立.
    </li>
    <li>利用<a class="ref" href="#cor-ka|kb"></a>.
        设 `d = (a_1, a_2, cdots, a_n)`, `d' = (k a_1, k a_2, cdots k a_n)`.
        一方面, `d | a_i`, 所以 `k d | k a_i`, `i = 1, 2, cdots, n`.
        这推出 `k d | d'`.<br/>
        另一方面, 由于 `k` 是 `k a_1, k a_2, cdots, k a_n` 的公约数, 所以
        `k | d'`. 又由 `d' | k a_i` 得 `d'//k | a_i`, `i = 1, 2, cdots,
        n`. 这推出 `d'//k | d`, 即 `d' | k d`.
    </li>
</ul>

<p class="remark">
    利用<a class="ref" href="#ppt-gcd"></a>,
    反复将一个数的 `k` 倍加到另一数上,
    就可以化简关系, 从而求出最大公约数.
    这种做法为后面的辗转相除法提供了思想. 一例:
    <span class="formula">
        `(-30; 45; -84)`
        `rarr (30; 45; 84)`
        `rarr (30; 15; 24)`
        `rarr (0; 15; 9)`
        `rarr (0; 6; 9)`
        `rarr (0; 6; 3)`
        `rarr (0; 0; 3)`
    </span>
    从而 (-30, 45, 84) = 3.
</p>

<h3>带余除法</h3>

<p>为进一步揭示最大公约数的性质, 我们引入有力工具——带余除法.</p>

<p class="theorem" id="the-division-algorithm">
    <b>带余除法</b>
	设 `n in ZZ`, `d in ZZ^**`, 则存在唯一的整数 `q` 与 `r`, 满足
	<span class="formula">
		`n = q d + r`, `quad 0 le r lt |d|`.
		<span class="label" id="for-division-algorithm"></span>
	</span>
	且 `d | n` 当且仅当 `r = 0`.
</p>

<ol class="proof">
	<li>唯一性. 若还有整数 `q', r'` 满足
		<a class="ref" href="#for-division-algorithm"></a>,
		不妨设 `r' ge r`, 于是
		<span class="formula">
			`r' - r = (q - q') d`,
			`quad 0 le r' - r lt |d|`.
		</span>
		由<a class="ref" href="#cor-div-order"></a>得 `r' - r = 0`.
		再由 `d != 0` 得 `q - q' = 0`.
	</li>
	<li>存在性. 当 `d | n` 时, 可取 `q = n//d`, `r = 0`.
		当 `d !| n` 时, 考虑集合
		<span class="formula">
			`T = {n-k d: k in ZZ}`.
		</span>
		容易看出 `T` 中含有正整数 (如取 `k = -2|n|d`),
        故可以设 `T` 中最小正整数为 `t_0 = n - k_0 d`.
		<br/>
		下证 `t_0 lt |d|`. 因为 `d !| n`, 所以 `t_0 != |d|`.
		若 `t_0 gt |d|`, 则 `t_1 = t_0 - |d| gt 0 in T`, 与 `t_0` 是
		`T` 的最小元素矛盾. 所以 `t_0 lt |d|`. 这时取 `q = k_0`,
		`r = t_0` 即满足要求.
	</li>
    <li>由 `n = q d + r` 知 `d | n iff d | r`,
        再由<a class="ref" href="#cor-div-order"></a>, `d | r iff r = 0`.
    </li>
</ol>

<p class="remark">
    带余除法中, `n, d, q, r` 分别称为<b>被除数, 除数, 商和余数</b>.
    带余除法是证明 `d | n` 这类命题的重要工具.
</p>

<h3>最大公约数的进一步性质</h3>

<p class="lemma" id="lem-d|ax+by">
    `a, b` 的公约数整除 `a, b` 的任意线性组合:
    <span class="formula">
        `d | a and d | b` `iff (AA x, y in ZZ)` `d | a x + b y`.
    </span>
</p>

<p class="proof">
    `lArr` 分别取 `(x, y) = (1, 0)` 和 `(0, 1)` 即可;<br/>
    `rArr` 设 `a = d a_1`, `b = d a_2`, 则
        `a x + b y = d (a_1 x + b_1 y)`.
</p>

<p class="theorem">
  <b>Bezout (裴蜀) 定理</b>
  设整数 `a, b` 不全为零, 则 `(a, b)` 是 `a, b` 的全体线性组合
  <span class="formula">
    `S = {a x+b y: x, y in ZZ}`
  </span>
  中的最小正整数.
</p>

<ol class="proof">
    显然 `S` 中含有正整数. 设 `s = a x+b y` 是其中的最小正整数.
    <li>由<a class="ref" href="#lem-d|ax+by"></a>知 `(a, b) | s`,
        这推出 `(a, b) le s`.
    </li>
    <li>由带余除法,
        <span class="formula">
            `a = s q + r`, `quad 0 le r lt s`,
        </span>
        注意到 `r in S`, 由 `s` 的最小性知 `r = 0`, 于是 `s | a`;
        同理 `s | b`. 因此 `s` 是 `a, b` 的公约数, `s le (a, b)`.
    </li>
</ol>

<p class="remark">
    `(a, b)` 是 `a, b` 的公约数集的最大元, 又是线性组合集的最小元,
    这样的对偶关系值得玩味.
</p>

<ol class="corollary">
    <li><b>公约数是最大公约数的约数</b>
        `d | a, d | b iff d | (a, b)`;
    </li>
    <li><b>公倍数是最小公倍数的倍数</b>
        `a | h, b | h iff [a, b] | h`.
    </li>
</ol>

<ol class="proof">
    <li>`lArr` 利用了最大公约数是一个公约数;
        `rArr` 利用了最大公约数是一个线性组合.
    </li>
    <li>`lArr` 显然, 下证 `rArr`. 记 `l = [a, b]`,
        作带余除法
        <span class="formula">
            `h = l q + r`, `quad 0 le r lt l`.
        </span>
        由 `a | h`, `b | h` 知 `a | r`, `b | r`,
        由最小公倍数的定义知 `r` 只能为 `0`, 因此 `l | h`.
    </li>
</ol>

<p class="proof">
    可以用 2. 来证 1.<br/>
    `lArr` 显然, 下证 `rArr`.  记 `g = (a, b)`,
    `h` 是 `a, b` 的全体公约数的最小公倍数.
    一方面, 由于 `g` 也是 `a, b` 的公约数, 有 `g | h`,
    这推出 `g le h`;<br/>
    另一方面, `a` 是 `a, b` 的全体公约数的一个公倍数, 由 1 有 `h | a`.
    同理 `h | b`. 这说明 `h` 是 `a, b` 的公约数, 故 `h le g`.
    综上 `g = h`, 即最大公约数是全体公约数的最小公倍数.
</p>

<h3>互素</h3>

<ol class="definition">
    <li>若 `(a, b) = 1`, 则称 `a, b` <b>互素</b>或<b>既约</b>;</li>
    <li>若 `(a_1, cdots, a_n) = 1`, 则称 `a_1, cdots, a_n` 这 `n`
        个数互素;
    </li>
    <li>若 `a_1, cdots, a_n` 中任意两个数都互素, 则称它们两两互素.</li>
    `n` 个数互素不常用, 但两两互素很常用.
</ol>

<p class="corollary">
    由 Bezout 定理,
    `a, b` 互素当且仅当 1 是它们的线性组合,
    即存在整数 `x, y` 使 `a x + b y = 1`.
</p>

<p class="proof">
    必要性显然, 下证充分性. 由于 1 是 `a, b` 的线性组合,
    故 `a, b` 的所有线性组合中的最小正整数是 1, 即 `(a, b) = 1`.
</p>

<ol class="property" id="ppt-coprime">
    设 `(a, b) = 1`,
    <li>`(a, b n) = (a, n)`, 特别有 `(a,b)=1`, `(a,n)=1`
      `rArr (a,b n)=1`;</li>
    <li>若 `a | b n`, 则 `a | n`;</li>
    <li>若 `a | n`, `b | n`, 则 `a b | n`.</li>
</ol>

<ol class="proof">
    <li>`(a, n) = (a, (a, b)n)`
        `= (a, (a n, b n))`
        `= ((a, a n), b n)`
        `= (a, b n)`.
    </li>
    <li>由 1. `(a, n) = (a, b n) = |a|`, 即 `a | n`.</li>
    <li>在 2. 中用 `n//b` 代替 `n`, 得到 `a | n//b`, 即 `a b | n`.</li>
</ol>

<p class="proof">
    2. 的另一证明: 利用 Bezout 定理,
    设 `1 = a x + b y`, `x, y` 为整数. 从而
    `a | a n x + b n y = n`.
</p>

<p class="theorem">
    设 `a, b` 是正整数, 则 `(a, b) [a, b] = a b`.
</p>

<p class="proof">
    记 `d = (a,b)`, `l = [a,b]`.
    一方面 `a | (a b)/d`, `b | (a b)/d`, 所以 `(a b)/d` 是 `a, b`
    的公倍数, 有 `l | (a b)/d`.<br/>
    另一方面
    由 `d(a/d, b/d) = (a, b) = d` 知 `(a/d, b/d) = 1`.
    而 `a/d | l/d`, `b/d | l/d`, 所以 `(a b)/d^2 | l/d`,
    即 `(a b)/d | l`.
</p>

<h3>辗转相除法 (Euclid 算法)</h3>

<p class="example">
    求 `(18, 25) = d`, 并找到 `x, y` 满足等式 `18 x + 25 y = d`.
</p>

<div class="solution">
<pre>
25 = (0, 1)
18 = (1, 0)
7 = (-1, 1)
4 = (3, -2)
3 = (-4, 3)
1 = (7, -5)
</pre>
因此 `18 * 7 - 25 * 5 = 1`.
</div>

<p class="theorem">
  <b>拉梅定理</b>
  Fibonacci 数定义为
  <span class="formula">
    `F_0 = F_1 = 1`, `quad F_(n+2) = F_(n+1) + F_n`.
  </span>
  正整数 `a gt b` 进行辗转相除, 若 `a // b` 的余数 `r_1 le F_n`,
  则除法的运算次数不超过 `n+1`.
</p>

<p class="proof">
  记第 `n` 次除法的余数为 `r_n`. 假设恰好作了 `n+1` 次除法,
  即 `r_(n+1) = 0`, 注意到辗转相除法中余数严格单调递减, 有
  <span class="formula">
    `r_n ge 1 = F_1`,<br>
    `r_(n-1) ge r_n+1 ge 2 = F_2`,<br>
    `r_(n-2) = r_(n-1) + r_n ge F_3`.
  </span>
  依此类推, 由归纳法得 `r_1 ge F_n`. 又注意到 `r_1 = F_n` 时,
  上式各等号均成立, 因此当 `a, b` 是相邻的 Fibonacci 数时为辗转相除法的最坏情形.
  于是 `r_1 le F_n` 时, 算上第一次得到 `r_1` 时所作的除法, 除法的运算次数不超过 `n+1`.
</p>

<h2>素数</h2>

<p class="definition">
	设 `n in ZZ`. 显然 `+-1, +-n` 是 `n` 的因子, 称为<b>平凡因子</b>.
    `n` 的其他因子称为<b>非平凡因子</b>或<b>真因子</b>.<br/>
    设 `n gt 1`, 如果 `n` 只有平凡因子, 则称它是<b>素数 (prime
	number)</b>; 否则称它是<b>合数 (composite number)</b>.
</p>

<p class="example">
	100 以内的素数有 25 个 (阴影部分):
</p>

<table id="primes">
</table>

<ol class="corollary" id="cor-prime-iff">
	<li>素数 `p` 的大于 1 的因子只有 `p` 自身;</li>
	<li>设 `n gt 1`. 则 `n` 是合数的充要条件是存在整数
		`1 lt a, b lt n`, 使得 `n = a b`.
	</li>
</ol>

<ol class="corollary">
    <b>互素与素数</b>
    设 `p` 是素数, 则
    <li>
        `(p, n) = {
            p, if p | n;
            1, if p !| n;
        :}`
        换言之, 要么 `n` 与 `p` 互素, 要么 `n` 是 `p` 的倍数.
    </li>
    <li>若 `p | a b`, 则 `p | a` 或 `p | b`.</li>
</ol>

<ol class="proof">
    <li>首先 `p | n iff (p, n) = p`. 若 `p !| n`, 有
        `(p, n) != p`, 因此 `(p, n)` 只能等于 `p` 的另一个正因子,
        即等于 1.
    </li>
    <li>设 `p !| a`, 由 1 知 `(p, a) = 1`,
        于是由<a class="ref" href="#ppt-coprime"></a>知 `p | b`.
    </li>
</ol>

<p class="theorem" id="the-composite-has-prime-divisor">
	合数必有素因子.
</p>

<p class="proof">
	设 `T` 是合数 `n` 的全体非平凡正因子的集合, 由定义 `T != O/`.
	由最小自然数原理, `T` 中有最小元素 `p`.
	若 `p` 是合数, 则 `p` 有非平凡因子 `d`, `1 lt d lt p`. 显然 `d in T`,
	这与 `p` 是 `T` 的最小元素矛盾. 故 `p` 是素数.
</p>

<p class="theorem">
	<b>算术基本定理 (唯一因子分解定理)</b>
	任意整数 `n gt 1` 可以表为素因子的乘积
	<span class="formula">
		`n = prod_(i=1)^s p_i`,
	</span>
	其中 `p_i` 是素数, `i = 1, 2, cdots, s`,
    不计素因子次序, 这种分解是唯一的.
	如果将相同的素因子合并, 上式可写为<b>标准分解式</b>
	<span class="formula">
		`n = prod_(i=1)^l p_i^(m_i)`,
	</span>
	其中 `m_i in NN` 是<b>重数</b>, `i = 1, 2, cdots, l`.
	换言之, 任意整数 `n gt 1` 都唯一对应着一个素数的<b>多重集合</b>
	<span class="formula">
		`{p_1: m_1, p_2: m_2, cdots, p_l: m_l}`.
	</span>
</p>

<p class="remark">
	算术基本定理是本章的主要结果, 也是数学中最重要和最基本的定理之一.
	在此后我们还要对它做进一步讨论. 这里先证明存在性, 唯一性留待以后证明.
</p>

<p class="proof">
	先证存在性.
	当 `n = 2` 时, 2 是素数, 所以结论成立.
	假设结论对任意整数 `1 lt a lt n` 都成立, 考虑 `n` 的情形.
	若 `n` 是素数, 结论已经成立; 若 `n` 是合数, 则由<a class="ref"
	href="#cor-prime-iff"></a>, 存在整数
	`1 lt n_1, n_2 lt n` 使得 `n = n_1 n_2`.
	由归纳假设, `n_1, n_2` 有素因子分解
	<span class="formula">
		`n_1 = prod_(i=1)^s p_i`, `quad n_2 = prod_(i=1)^t q_i`.
	</span>
	于是 `n = p_1 p_2 cdots p_s q_1 q_2 cdots q_t`.
	由第二数学归纳法, 存在性得证.
</p>

<ol class="corollary">
	设 `n gt 1`,
	<li>若 `n` 是合数, 则 `n` 有不超过 `sqrt n` 的素因子;</li>
	<li>若 `n` 可以表为 `s` 个素因子的乘积, 则 `n` 有不超过 `n^(1/s)`
		的素因子.
	</li>
</ol>

<p class="algorithm">
	<b>Eratoschenes 筛法</b>, <b>Euler 筛法</b>:
    参看计算机笔记.
</p>

<p class="theorem" id="the-primes-inf">
	素数有无穷多个.
</p>

<p class="proof">
	反设素数有限, 为 `p_1, p_2, cdots, p_n`.
	考虑 `a = prod_(i=1)^n p_i + 1`, 显然 `a` 大于任意一个素数,
	因此是合数.
	由<a class="ref" href="#the-composite-has-prime-divisor"></a>,
	`a` 有素因子 `p | a`. 设 `p = p_j`, 则
	<span class="formula">
		`p = p_j | a - prod_(i=1)^n p_i = 1`,
	</span>
	与 `p ge 2` 矛盾.
</p>

<ol class="theorem">
	用 `pi(n)` 表示不超过 `n` 的素数的个数. 用 `p_n` 表示第 `n` 个素数
	(`p_1 = 2`). 则
	<li>`p_n le 2^(2^(n-1))`, `n = 1, 2, cdots`;</li>
	<li>`pi(n) gt log_2 log_2 n`, `n = 2, 3, cdots`.</li>
</ol>

<ol class="proof">
	<li>由<a class="ref" href="#the-primes-inf"></a>的证明知
		<span class="formula">
			`p_(n+1) le prod_(i=1)^n p_i + 1`, `n = 1, 2, cdots`.
		</span>
		`n = 1` 时, 结论 1 显然成立.
		现在设结论 1 对任意整数 `1 le i le n` 成立, 考虑 `n+1` 的情形.
		由上式及归纳假设得
		<span class="formula">
			`  p_(n+1)
			le prod_(i=1)^n 2^(2^(i-1)) + 1`
            `= 2^(sum_(i=1)^n 2^(i-1)) + 1`
			`=  2^(2^n-1) + 1
			lt 2^(2^n-1) + 2^(2^n-1)
			=  2^(2^n)`.
		</span>
		由第二数学归纳法知结论 1 成立.
	</li>
	<li>对 `n ge 2`, 由最大自然数原理, 必有唯一的正整数 `k`, 使得
		<span class="formula">
			`2^(2^(k-1)) le n lt 2^(2^k)`,
		</span>
		利用 `pi(n)` 的单调性,
		<span class="formula">
			`pi(n) ge pi(2^(2^(k-1))) ge k gt log_2 log_2 n`.
		</span>
	</li>
</ol>

<p class="remark">
	今后我们会介绍 `p_n` 与 `pi(n)` 的更好的估计.
</p>

<h3>Fermat 小定理</h3>

<p class="lemma">
  <b>Frobenius 自同构</b> ??
  对任意整数 `a, b`, 素数 `p` 和非负整数 `n` 有
  <span class="formula">
    `(a+b)^(p^n) -= a^(p^n) + b^(p^n) (mod p)`,
  </span>
  特别 `(a+b)^p -= a^p + b^p (mod p)`.
</p>

<ol class="theorem">
    设 `p` 是素数, 则
    <li>`p | (p;k)`, `1 le k le p-1`.</li>
    <li>`p | a^p - a`, `a in NN`.</li>
    <li><b>Fermat 小定理</b> 若 `(a, p) = 1`, 则 `p | a^(p-1)-1`;
        换言之, `a^(p-1) -= 1` `(mod p)`.
    </li>
</ol>

<ol class="proof">
    <li>直观地看, `p` 整除 `(p;k) = (p!)/(k!(p-k)!)` 的分子, 而不整除分母,
		因此 `p` 整除 `(p;k)`. 下面给出正式证明:
		因为 `p` 是素数, 所以对任意 `1 le k le p-1` 有
        `(p, k) = 1`. 反复运用<a class="ref"
            href="#ppt-coprime"></a>的 1 得到 `(p, k!) = 1`.
        现在记
        <span class="formula">
            `(p;k) = (p(p-1) cdots (p-k+1))/(k!) := (p a)/(k!)`,
        </span>
        因为 `(p;k)` 是整数, 有 `k! | p a`.
        再运用<a class="ref" href="#ppt-coprime"></a>的 2, 有
        `k! | a`. 这说明 `a//k!` 是整数, 所以 `p | (p;k)`.
    </li>
    <li>`a = 1` 时显然成立. 假设 `a = n` 时结论成立, 则
        <span class="formula">
            `(n+1)^p - (n+1)`
            `-= n^p + (p;1) n^(p-1) + cdots + (p;p-1) n + 1 - (n+1)`
            `-= n^p - n`
            `-= 0` `(mod p)`.
        </span>
    </li>
    <li>由 2. 和<a class="ref" href="#ppt-coprime"></a>的 2.
        即得结论.
    </li>
</ol>

<p class="example">
    利用 Fermat 小定理计算 `2^100` 除以 `13` 的余数.
</p>

<p class="solution">
    这里 `p = 13`. 由 Fermat 小定理, `2^12 -= 1` `(mod 13)`.
    <span class="formula">
        `2^100 -= 2^(12 xx 8 + 4)`
        `-= (2^12)^8 * 2^4`
        `-= 2^4 -= 3` `(mod 13)`.
    </span>
</p>

<p class="example">
    `AA a in NN`, `2730 | a^13-a`.
</p>

<p class="proof">
    设 `d | 12`, 则 `a^d-1 | a^12-1`.
    若 `d = p-1`, `p` 为素数, 由 Fermat 小定理有
    <span class="formula">
        `p | a^p-a`
        `= a(a^d-1) | a(a^12-1)`.
    </span>
    列出 12 的所有正因数 1, 2, 3, 4, 6, 12, 再分别加 1 得
    2, 3, 4, 5, 7, 13, 其中素数有 2, 3, 5, 7, 13.
    所以 `2730 = 2 xx 3 xx 7 xx 13 | a^13-a`.
</p>

<p class="example">
    对任意整数 `n`, `15 | 3n^5+5n^3+7n`.
</p>

<p class="proof">
    由 Fermat 小定理, `n^p - n -= 0 (mod p)`. 于是
    <span class="formula">
        `3n^5+5n^3+7n -= 5(n^3-n) + 5n + 7n -= 0 (mod 3)`,<br/>
        `3n^5+5n^3+7n -= 3(n^5-n) + 3n + 7n -= 0 (mod 5)`.
    </span>
</p>

<h3>`p` 进制数</h3>

<p>[来自 <a href="http://www.aquatutoring.org/KummerTheoremLucasTheorem.pdf">KummerTheoremLucasTheorem</a>]</p>

<p class="definition">
  若素数 `p` 和正整数 `n` 满足 `p^k | n`, `p^(k+1) !| n`, 则称 `p` 在 `n`
  中的次数是 `k`, 或者称 `n` 的 <b>`bm p` 进制值 (`bm p`-adic valuation)</b>
  `v_p(n) = k`. 显然 `v_p` 是积性函数, 满足
  <span class="formula">
    `v_p(m n) = v_p(m) v_p(n)`.
  </span>
</p>

<p class="example">
  `n!` 末尾有多少个零?
</p>

<p class="solution">
  即求 `5` 在 `n!` 中的次数.
  因为 `n` 以内的正整数中, `5` 的倍数有
  `|__n/5__|` 个, 它们为乘积 `n!` 提供了 `|__n/5__|` 个 `5` 的因子.
  在这些 `5` 的倍数中, `5^2` 的倍数有 `|__n/5^2__|` 个, 为乘积 `n!`
  提供了额外的 `|__n/5^2__|` 个 `5` 的因子. 依次类推, `n!` 中, `5`
  的次数等于
  <span class="formula">
    `sum_(i ge 1) |__n/5^i__|`.
  </span>
  上式是无穷级数, 但只有有限项不为零.
</p>

<ol class="corollary">
  <li>`v_p(n!) = sum_(i ge 1) |__n/p^i__|`;</li>
  <li>`v_p(n;k) = v_p(n!) - v_p(k!) - v_p((n-k)!)`.</li>
</ol>

<p class="lemma">
  <b>Legendre 公式</b>
  `p` 为素数, 将正整数 `n` 写为 `p` 进制 `n = sum_(i=0)^k a_i p^i`,
  记 `s_p(n) = sum_(i=0)^k a_i`, 有
  <span class="formula">
    `v_p(n!) = (n - s_p(n))/(p-1)`.
  </span>
</p>

<p class="proof">
  <span class="formula">
    `v_p(n!) = sum_(i ge 1) |__n/p^i__|`
    `= (a_1 + cdots + a_k p^(k-1))`
    `+ (a_2 + cdots + a_k p^(k-2))`
    `+ cdots + a_k`
    `= a_1 + a_2 (1+p) + cdots + a_k(1+p+cdots+p^(k-1))`
    `= [a_1(p-1) + a_2(p^2-1) + cdots + a_k(p^k-1)]//(p-1)`
    `= (n - s_p(n))/(p-1)`.
  </span>
</p>

<p class="theorem">
  <b>Kummer 定理</b> `p` 为素数,
  将 `m, n` 写为 `p` 进制数然后相加, 进位的次数恰等于 `v_p(m+n;n)`.
</p>

<p class="proof">
  记
  <span class="formula">
    `m+n = sum_(i=0)^r a_i p^i`,
    `quad m = sum_(i=0)^r b_i p^i`,
    `quad n = sum_(i=0)^r c_i p^i`,
  </span>
  如果三个数的位数不同, 可以在 `m, n` 的开头补零使它们相同.
  定义进位函数 `gamma` 如下: `gamma_(-1) = gamma_r = 0`, `0 le i lt r` 时,
  <span class="formula">
  `gamma_i = {
     1, if b_i + c_i + gamma_(i-1) ge p;
     0, otherwise;
  :}`
  </span>
  根据加法法则, 我们有
  <span class="formula">
    `a_i = b_i + c_i + gamma_(i-1) - p gamma_i`, `quad i = 0, cdots, r`.
  </span>
  求和得
  <span class="formula">
    `s_p(m+n) - s_p(m) - s_p(n)`
    `= sum_(i=1)^r gamma_(i-1) - sum_(i=0)^(r-1) p gamma_i`
    `= (1-p) sum_(i=0)^(r-1) gamma_i`.
  </span>
  现在应用 Legendre 公式有
  <span class="formula">
    `v_p (m+n; n)`
    `= v_p((m+n)!) - v_p(m!) - v_p(n!)`
    `= (s_p(m) + s_p(n) - s_p(m+n))/(p-1)`
    `= sum_(i=0)^(r-1) gamma_i`,
  </span>
  这正是进位的次数.
</p>

<p class="theorem">
  <b>Lucas 定理</b>
  `p` 为素数, 计算 `(m; n) mod p`. 先将 `m, n` 写为 `p` 进制数:
  <span class="formula">
    `m = sum_(i=0)^k a_i p^i`,
    `quad n = sum_(i=0)^k b_i p^i`,
  </span>
  则有
  <span class="formula">
    `(m; n) -= prod_(i=0)^k (a_i; b_i) (mod p)`.
  </span>
  特别 `(m; n)` 是奇数当且仅当它们的二进制表示满足 `a_i ge b_i`, `i = 0,
  cdots, k`.
</p>

<p class="proof">
  考虑 `(1+x)^m` 的 `n` 次项系数 `(m; n)`, 利用 Frobenius 引理有
  <span class="formula">
    `(1+x)^m`
    `= (1+x)^(sum_(i=0)^k a_i p^i)`
    `= prod_(i=0)^k (1+x)^(a_i p^i)`
    `-= prod_(i=0)^k (1+x^(p^i))^(a_i)`
    `= prod_(i=0)^k sum_(j_i=0)^(a_i) (a_i; j_i) x^(j_i p^i) (mod p)`.
  </span>
  考虑上式右端的 `n` 次项系数, 这只需从乘积的因子中各取一项
  `(a_i; j_i) x^(j_i p^i)` 相乘即可. 它们的次数之和满足
  <span class="formula">
    `sum_(i=0)^k p^i j_i = n`.
  </span>
  由 `p` 进制表示的唯一性知道 `j_i = b_i`, `i = 0, cdots, k`, 于是所求的
  `n` 次项系数是
  <span class="formula">
    `prod_(i=0)^k (a_i; b_i) (mod p)`.
  </span>
</p>

<h2>杂例</h2>

<p class="example">
	设 `n in NN\\{1}`, `0 le r lt n`. 记全体模 `n` 余数等于 `r` 的整数为
	<span class="formula">
		`S_(n,r) = {kn + r: k in ZZ}`.
	</span>
	我们有
	<span class="formula">
		`uuu_(r=0)^(n-1) S_(n,r) = ZZ`; `quad`
		`S_(n,r_1) nn S_(n,r_2) = O/`, `r_1 != r_2`.
	</span>
	即全体整数按模 `n` 的余数分为 `n` 个类, 称为<b>模 `n` 的同余类</b>.
	在每一同余类中的数模 `n` 后有相同余数, 称它们<b>模 `n` 同余</b>,
	记为 `a -= b (mod n)`. 显然
	<span class="formula">
		`a -= b (mod n) iff n | a - b`.
	</span>
</p>

<p class="example">
	<b>除以 7, 11, 13 的余数</b>
	一个前三位和后三位数字完全相同的六位数 (如, 123123)
	显然是 1001 的倍数.  注意到 `1001 = 7 xx 11 xx 13`,
	因此我们可以反复从一个数中减去 1001 的倍数, 来计算这个数除以
	7 (或 11, 13) 的余数. 如考虑 142857, 有
	<span class="formula">
		`142857 -= 142857 - 142142 -= 715 -= 1 (mod 7)`.
	</span>
	类似地, 利用 `17 | 10^8+1` 可以计算除以 17 的余数,
	只不过计算量更大了.
</p>

<ol class="example">
	<b>完全平方数</b> (简称平方数)
    是指能写成整数的平方的数, 如 0, 1, 4, 9 等.
	设 `n` 是正整数, 则
	<li>`n^2` 除以 10 的余数是 0, 1, 4, 5, 6 或 9;</li>
	<li>`n^2` 除以 9 的余数是 0, 1, 4 或 7;</li>
	<li>`n^2` 除以 16 的余数是 0, 1, 4 或 9;</li>
	<li>如果 `n^2` 的个位是奇数, 则它是十位是偶数;</li>
	<li>`n^2` 的个位等于 6 当且仅当它的十位是奇数.</li>
</ol>

<p class="example">
	设 `a in NN\\{1}`, `n in NN`. 则 `n` 可以唯一地表为
	<span class="formula">
		`n = sum_(i=0)^m r_i a^i`, `quad`
		`m ge 0`, `0 le r_i lt a`, `i = 0, 1, cdots, m`.
	</span>
	称为正整数 `n` 的 <b>`a` 进位 (base-`a` 或 radix-`a`) 表示</b>.
</p>

<p class="proof">
	由最大自然数原理, 对正整数 `n` 存在唯一的 `m ge 0`, 使
	`a^m le n lt a^(m+1)`.
	由带余除法, 存在唯一的 `q, r` 满足
	<span class="formula">
		`n = a q + r`, `quad 0 le r lt a`.
	</span>
	对 `m` 使用数学归纳法.
	若 `m = 0`, 则必有 `q = 0`, `1 le r lt a`, 所以结论成立.
	设结论对整数 `m ge 0` 成立, 考虑 `m+1` 的情形.
	因为 `a^(m+1) le n lt a^(m+2)`,
	所以上式中的 `q` 满足 `a^m le q lt a^(m+1)`.
	由归纳假设, 存在唯一的 `0 le s_i lt a`, `i=0,1,cdots,m`, 使
	<span class="formula">
		`q = sum_(i=0)^m s_i a^i`.
	</span>
	所以
	<span class="formula">
		`n = a sum_(i=0)^m s_i a^i + r
		= r + sum_(i=1)^(m+1) s_(i-1) a^i`,
	</span>
	即结论对 `m+1` 成立.
</p>

<ol class="example">
    研究幂函数 `f(n) = n^k`, `k` 为正整数.
    <li>`a^k | b^k iff a | b`</li>
    <li>`(a^k, b^k) = (a, b)^k`.</li>
    <li>设 `a, b` 互素, 且 `a b = n^k`,
        则 `a, b` 都是某个数的 `k` 次方.
    </li>
</ol>

<ol class="proof">
    <li>`lArr` 显然, 下证 `rArr`. 先设 `a, b` 互素, 则由 `a | b^k`
        和<a class="ref" href="#ppt-coprime"></a>知 `a | b`. 再证一般情形.
        设 `(a, b) = d`, 由 `a^k | b^k` 得 `(a/d)^k | (b/d)^k`,
        由互素情形知 `a/d | b/d`, 即 `a | b`.
    </li>
    <li>先设 `a, b` 互素, 则由<a class="ref" href="#ppt-coprime"></a>,
        <span class="formula">
            `(a^k, b) = (1, b) = 1`,
        </span>
        因此 `a^k, b` 互素. 再用<a class="ref" href="#ppt-coprime"></a>,
        <span class="formula">
            `(a^k, b^k) = (a^k, 1) = 1`.
        </span>
        再证一般情形. 设 `(a, b) = d`, 则
        <span class="formula">
            `(a^k, b^k) = d^k ((a/d)^k, (b/d)^k)`
        </span>
        由互素情形知上式右边等于 `d^k`.
    </li>
    <li>`(a, n)^k = (a^k, n^k)`
        `= (a^k, a b) = a (a^(k-1), b) = a`.
        同理 `(b, n)^k = b`.
    </li>
</ol>

<ol class="example">
    研究指数函数 `f(n) = c^n - 1`, 其中整数 `c gt 1`.
    <li>`c^a - 1 | c^b - 1 iff a | b`;</li>
    <li>`(c^a-1, c^b-1) = c^((a,b))-1`;</li>
    今后我们将用指数和原根来研究这个函数.
</ol>

<ol class="proof">
    <li>`lArr`. 利用因式分解
        <span class="formula">
            `c^d - 1 = (c-1)(1+c+cdots+c^(d-1))`
        </span>
        知, `c-1 | c^d-1`. 设 `b = a d`, 用 `c^a` 代替公式中的 `c` 得
        <span class="formula">
            `c^a-1 | c^(a d) - 1 = c^b - 1`.
        </span>
        `rArr`. 作带余除法
        <span class="formula">
            `b = q a + r`, `quad 0 le r lt a`,
        </span>
        于是
        <span class="formula">
            `c^b - 1`
            `= c^(q a + r) - c^r + c^r - 1`
            `= c^r(c^(q a) - 1) + c^r - 1`.
        </span>
        由 `c^a - 1 | c^b - 1` 知 `c^a - 1 | c^r - 1`, 然而 `c^a - 1 gt
        c^r - 1`, 故 `c^r-1 = 0`, 即 `r = 0`.
    </li>
    <li>不妨设 `a ge b`, 有
        <span class="formula">
            `(c^a-1, c^b-1)`
            `= ((c^a-1) - (c^b-1), c^b-1)`
            `= (c^b(c^(a-b)-1), c^b-1)`
            `= (c^(a-b)-1, c^b-1)`.
        </span>
        注意指数已经从 `a` 变为 `a-b`. 反复使用这一结果, 类似辗转相除法,
        最终就得到 `c^((a,b))-1`.
    </li>
</ol>

<script>
(function(){
function isprime(n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 6 !== 1 && n % 6 !== 5) return false;
    for (var i = 5; i*i <= n; i += 6) {
        if (n % i === 0 || n % (i+2) === 0)
            return false;
    }
    return true;
}
var buf = [];
for (var i = 0; i < 10; ++i) {
    buf.push('<tr>')
    for (var j = 1; j <= 10; ++j) {
        var n = 10 * i + j;
        if (isprime(n)) {
            buf.push('<td class="shadow">' + n + '</td>');
        } else {
            buf.push('<td>' + n + '</td>');
        }
    }
    buf.push('</tr>');
}
document.getElementById('primes').innerHTML = buf.join('\n');
})();
</script>

<script src="../../js/note.js?type=math"></script>
</body>
</html>
